class Solution(object):
    def minMalwareSpread(self, graph, initial):
        n = len(graph)
        eyi_rank = [0] * n
        for index in initial:
            eyi_rank[index] = 1

        def find(x):
            if p[x] == x:
                return p[x]
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rx = find(x)
            ry = find(y)
            if rx != ry:
                if rx > ry:
                    p[rx] = ry
                    rank[ry] += rank[rx]
                    new_eyi[ry] += new_eyi[rx]
                    rank[rx] = 0
                    new_eyi[rx] = 0
                else:
                    p[ry] = rx
                    rank[rx] += rank[ry]
                    new_eyi[rx] += new_eyi[ry]
                    rank[ry] = 0
                    new_eyi[ry] = 0

        max_val = 0
        ans = n
        for index in initial:
            p = [i for i in range(n)]
            new_eyi = eyi_rank.copy()
            new_eyi[index] = 0
            rank = [1] * n
            for i in range(n):
                if i != index:
                    for j in range(i + 1, n):
                        if j != index:
                            if graph[i][j]:
                                union(i, j)
            now = 0
            for i in range(n):
                if new_eyi[i] == 0:
                    now += rank[i]
            if now > max_val:
                ans = index
                max_val = now
            else:
                if now == max_val:
                    ans = min(ans, index)
        return ans


data = Solution()
graph = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
initial = [0, 1]
print(data.minMalwareSpread(graph, initial))
graph = [[1, 1, 0], [1, 1, 1], [0, 1, 1]]
initial = [0, 1]
print(data.minMalwareSpread(graph, initial))
graph = [[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 1, 1], [0, 0, 1, 1]]
initial = [0, 1]
print(data.minMalwareSpread(graph, initial))
